#include <iostream>

// 策略模式（有纯虚函数的支持才能实现）
// 抽象类：具有纯虚函数的类，不允许实例化对象，就是作为一个模板形式存在的
class Sort
{
public:
    // 纯虚函数（前面加virtual，后面=0）
    virtual void sort(int *a, int size) = 0;    
};

// 没实现父类的纯虚函数，子类仍然是抽象类
class BubbleSort:public Sort
{
public:
    // 子类继承父类的虚函数，那这个函数仍为虚函数，也就是前面virtual可加可不加
    void sort(int *a, int size)
    {
        std::cout<<"冒泡排序"<<std::endl;
        for(int i = 0; i <size - 1; i++)
        {
            for(int j = 0; j < size - i - 1; j++)
            {
                if(a[j] > a[j+1])
                std::swap(a[j], a[j+1]);
            }
        }
    }
};

class FastSort:public Sort
{
public:
    // 对外公开的函数
    void sort(int *a, int size)
    {
        std::cout<<"快速排序"<<std::endl;
        FSort(a, 0, size - 1);
    }
private:
    // 对内公开的函数
    void FSort(int *a, int start, int end)
    {
        if(start >= end)
            return;
        int left = start;
        int right = end;
        int temp = a[left];
        while(left < right)
        {
            while(a[right] > temp && left < right)
                right--;
            if(left < right)
                a[left++] = a[right];
            while(a[left] < temp && left <right)
                left++;
            if(left < right)
                a[right--] = a[left];
        }
        a[left] = temp;
        FSort(a, start, left - 1);
        FSort(a, right + 1, end);
    }
};

// 真正排序的地方已经不再动了，只要根据外部的传参，反正统一都是Sort类型的指针
// 完全符合开闭原则
void S(Sort *s)
{
    int a[] = {3, 1, 2};
    s->sort(a, 3);
    for(int i = 0; i < 3; i++)
    {
        std::cout<<a[i]<<" ";
    }
    std::cout<<std::endl;
}

int main()
{
    Sort *s1 = new BubbleSort;
    Sort *s2 = new FastSort;

    S(s2); // 这样就实现了将对象和函数实现隔离开来，想实现什么排序就传什么指针
    return 0;
}